package demo;

import java.util.Arrays;

public class CreateHeap {

    public static void createHeap(int[]array){
        //建堆从完全二叉树的最后一个根结点开始向下调整
        int size=array.length;
        for(int i=(size-1-1)/2;i>=0;i--){
            shiftDown2(array,i);
        }

    }
    public static void createHeap2(int[]array) {
        //建堆从完全二叉树的最后一个根结点开始向下调整
        int size = array.length;
        for (int i = (size - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(array, i);
        }
    }
    //向下调整（最大堆）
    public static void shiftDown2(int []array,int index){
        int size=array.length;
        while(true){
            int leftIdx=2*index+1;
            //是否有叶子结点
            if(leftIdx>=size){
                return ;
            }
            //有 假设左孩子最大
            int maxIdx=leftIdx;
            if(leftIdx+1<size&&array[leftIdx+1]>array[leftIdx]){
                //右孩子最大不成立
                maxIdx=leftIdx+1;
            }
            //根已经最大不用调整
            if(array[index]>=array[maxIdx]){
                return ;
            }
            swap(array,maxIdx,index);
            index=maxIdx;
        }
    }

    //向下调整（最小堆）
    public static void shiftDown(int[]array,int index){
        int size=array.length;
        while(true){
            int leftIdx=2*index+1;

            if(leftIdx>=size){
                return ;
            }
            int minIdx=leftIdx;
            if(leftIdx+1<size&&array[leftIdx+1]<array[leftIdx]){
                minIdx=leftIdx+1;
            }
            if(array[minIdx]>array[index]){
                return ;
            }
            swap(array,minIdx,index);
            index=minIdx;


        }

    }
    private static void swap(int[]array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }

    public static void main(String[] args) {
        int[]arr={1,5,3,8,7,6};
        createHeap(arr);
        System.out.println(Arrays.toString(arr));

        int[]arr2={8,7,6,5,1,3};
        createHeap2(arr2);
        System.out.println(Arrays.toString(arr2));
    }


}
